#include <bits/stdc++.h>
using namespace std;
const int N = 300010;
typedef unsigned long long ull;
ull f[N + 1], power[N + 1];
int sa[N + 1], rk[N + 1], height[N + 1], n;
char str[N];
ull get_hash(int l, int r) { return f[r] - f[l - 1] * power[r - l + 1]; }
int lcp(int x, int y) {
  int l = 0, r = min(n - x + 1, n - y + 1);
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (get_hash(x, x + mid - 1) == get_hash(y, y + mid - 1))
      l = mid;
    else
      r = mid - 1;
  }
  return l;
}
bool cmp(int x, int y) {
  int l = lcp(x, y);
  return str[x + l] < str[y + l];
}
void calc_height() {
  for (int i = 2; i <= n; ++i) height[i] = lcp(sa[i - 1], sa[i]);
}
int main() {
  scanf("%s", str + 1);
  n = strlen(str + 1);
  power[0] = 1;
  for (int i = 1; i <= n; ++i) {
    sa[i] = i;
    f[i] = f[i - 1] * 131 + str[i] - 'a' + 1;
    power[i] = power[i - 1] * 131;
  }
  sort(sa + 1, sa + n + 1, cmp);
  calc_height();
  for (int i = 1; i <= n; ++i) printf("%d ", sa[i] - 1);
  puts("");
  for (int i = 1; i <= n; ++i) printf("%d ", height[i]);
  puts("");
}
